/**
 * @file filename.cpp
 * @brief nullptr关键字用于标识空指针，与NULL不同，NULL为0
 * @author Monomania (1301519350@qq.com)
 * @version 0.1
 * @date 2021-09-23
 */
#include<iostream>
#include <vector> 
#include <string>
#include <list>
#include <map>
#include <algorithm> // std::minmax_element
#include <boost/algorithm/string.hpp>
#include <functional>
#include <iterator>
// #define NDEBUG
#include <assert.h>
using namespace std;

#define OK 1
#define ERROR 0
#define TRUE true
#define FALSE false
// 定义一个不可能的数
#define INF   -99999  
#define MAXSIZE 20 /* 存储空间初始分配量 */

typedef int Status; 
typedef int SElemType; /* SElemType类型根据实际情况而定，这里假设为int */


class Solution {
public:
    string addBinary(string a, string b) 
    {
        string result;
        /*将两个字符串反转，方便后面的计算(因为是按低位到高位进行计算的，但由于两字符串长度不一定一致，
          又因为其低位的下标为数组下标最大值，所以不好操作，将字符串先反转后再从下标0开始遍历尽心加法运算)
        */
        reverse(a.begin(),a.end());
        reverse(b.begin(),b.end());
        int maxlen=max(a.size(),b.size()),minlen=min(a.size(),b.size()),add=0;//add为进位标志
        for(int i=0;i<maxlen;i++)
        {
            if(i>minlen-1)//对长度较小的字符串后边增加'0'字符
            {
                if(a.size()>b.size())
                    b=b+'0';
                else
                    a=a+'0';
            }
            result.push_back((add+a[i]+b[i]-96)%2+48);
            //当前位=（上一个进位+a[i]+b[i]）%2，其中-96是因为要转化为十进制数，后面的+48是ASCII表中数字与字符的差值
            add=(add+a[i]+b[i]-96)/2;//与上面原因一样
        }
        if(add)//判断最后进位是否为1，若为1则在字符串后+'1'
            result.push_back('1');
        reverse(result.begin(),result.end());//将相加后的字符串再次反转则为答案
        return result;
    }
};


int main(int argc, const char** argv) {
    Solution solu = Solution();
    string a = "11", b = "1";

    cout << solu.addBinary(a, b) << endl;

    return 0;
}